package realQuestion.yongyou;

import java.util.Arrays;

public class Main3 {


    public int minimumCost (int n, int[][] connections) {
        // write code here
        UnionFind unionFind = new UnionFind(n);
        Arrays.sort(connections,(a,b)->a[2]-b[2]);
        int energy=0;
        int count=0;

        for (int [] con:connections){
            int x = con[0];
            int y = con[1];
            int cost=con[2];

            if (unionFind.union(x,y)){
                energy+=cost;
                count++;

                if (count==n-1){
                    break;
                }
            }

        }
        if (count!=n-1){
            return  -1;
        }
        return  energy;


    }

    class  UnionFind{
        private int[]  parent;
        private  int[]  size;


        public  UnionFind(int n){
            parent=new int[n+1];
            size=new int[n+1];

            for (int i = 1; i <=n ; i++) {
                parent[i]=i;
                size[i]=1;
            }

        }
        int find(int x){
            if (parent[x]!=x){
                parent[x]=find(parent[x]);
            }
            return parent[x];
        }
        boolean union(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            if (rootX==rootY){
                return  false;
            }
            if (size[rootX]<size[rootY]){
                parent[rootX]=rootY;
                size[rootY]+=size[rootX];
            }else {
                parent[rootY]=rootX;
                size[rootX]+=size[rootY];
            }
            return  true;

        }

    }
}
